home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.mactech.com 2010
/
ftp.mactech.com.tar
/
ftp.mactech.com
/
challenge
/
13.06
/
ChallengeHexGame.sit.hqx
/
Challenge, Hex Game
/
Hex Strategy.c
< prev
next >
Wrap
Text File
|
1997-05-07
|
39KB
|
1,367 lines
// *********************************************************
// Programmer: Gregory Cooper
// Date: Februrary 22, 1997
// Function: a strategy for the game of Hex
// Written for: March, 1997 MacTech Programmer's Challenge
//
// General idea: My strategy tries to find the quickest
// routes across the board, both for itself and for its
// opponent. If the opponent has a better, shorter route
// than my strategy does, then my strategy makes a defensive
// move (one that makes it more difficult for the opponent
// to complete his route). Otherwise, it makes an offensive
// move (one which brings its own route closer to
// completion). It re-traces the routes during each turn,
// looking for necessary modifications and scoring changes.
// *********************************************************
#include "Storage.h"
// an enumeration for move types
typedef enum
{
// counter-clockwise from right
right, // 0
upRightTwoBridge, // 30
upRight, // 60
upTwoBridge, // 90
upLeft, // 120
upLeftTwoBridge, // 150
left, // 180
downLeftTwoBridge, // 210
downLeft, // 240
downTwoBridge, // 270
downRight, // 300
downRightTwoBridge, // 330
noDirection // undefined
} Direction;
// a data structure for representing potential routes to
// edges or to other chips
typedef struct Path
{
long row; // row of piece on board
long col; // column of piece on board
Direction nextDirection; // direction to next piece
Direction prevDirection; // direction to prev piece
Boolean occupied; // location actually taken?
Boolean center; // origin of path?
struct Path *next; // next piece in path
struct Path *prev; // previous piece in path
} Path;
// a data type for the playing chips
typedef enum
{
empty,
blue, // plays first
red // plays second
} Chip;
// an enumeration for disposing of unneeded paths
// (used by the BetterPath function and its clients)
typedef enum
{
leaveBad, // indicates that inferior strategy should
// be left alone
forgetBad // indicates that inferior strategy should
// be disposed
} PathAction;
// an enumeration for the edges
typedef enum
{
leftEdge,
rightEdge,
topEdge,
bottomEdge
} Edge;
// an enumeration for path disruptions
typedef enum
{
noDisruption, // move did not block path
inTwoBridge, // move occupied part of a two-bridge
inSpot // move occupied a strategic location
} Disruption;
Path *BestPathAcrossBoard(long boardSize, Chip *theBoard,
long startRow, long startCol, Chip color);
// tries to find a path across the board through
// (startRow, startCol)
// PRECONDITIONS: boardSize is the number of rows or columns
// on the board; theBoard stores information about the
// board; (startRow, startCol) indicates a piece of the
// given color on the board; color indicates which player
// for whom the path is to be found
// POSTCONDITIONS: returns a pointer to the path found,
// beginning with (startRow, startCol), or returns nil
// if no path exists
Boolean ExtendPathToEdge(long boardSize, Chip *theBoard,
Path *path, Edge edge);
// tries to find a path from path to the given edge
// PRECONDITIONS: path is an incomplete path, edge is one
// of the four edges, boardSize is the number of rows or
// columns on the board, theBoard defines the playing board
// POSTCONDITIONS: if a path from the edge exists, it is
// found and the value true is returned; otherwise, all
// memory associated with the path is freed and it returns
// false
void PrioritizeMoves(Edge edge, Direction moveList[12]);
// determines the order in which potential moves in a path
// should be attempted
// PRECONDITIONS: edge is the edge to which we are trying
// to move
// POSTCONDITIONS: moveList contains the moves in order
// from most to least direct
Boolean PossibleMove(long boardSize, Chip *theBoard,
long row, long col, Path *path, Direction move,
Chip color);
// determines whether placing a piece in a given location
// is feasible
// PRECONDITIONS: boardSize is the number of rows or columns
// on the board; theBoard defines the board; (row, col)
// is the piece from which we are moving; move is the
// direction in which we are moving; color is the color of
// the player
// POSTCONDITIONS: returns true if the given move is
// possible, false otherwise
void FindNewLocation(long row, long col, Direction move,
long *newRow, long *newCol);
// determines the location of a piece adjacent to another
// piece in a given direction
// PRECONDITIONS: (row, col) indicates the initial piece,
// move is the direction of the move
// POSTCONDITIONS: (*newRow, *newCol) contain the location
// of the new piece
Direction OppositeDirection(Direction move);
// determines the direction opposite a given direction
// PRECONDITIONS: move is a direction
// POSTCONDITIONS: returns the direction opposite move
Boolean OnBoard(long boardSize, long row, long col);
// determines whether a given piece lies on the board
// PRECONDITIONS: boardSize is the size of the board,
// (row, col) is the location of the desired piece
// POSTCONDITIONS: returns whether the piece is
// within the boundaries of the board
Boolean IsTwoBridge(Direction move);
// determines whether a connection in a given direction is
// a two-bridge
// PRECONDITIONS: move is the direction of the desired
// connection
// POSTCONDITIONS: returns true if the connection is a
// two-bridge; otherwise returns false
Boolean TwoBridgeFree(long boardSize, Chip *theBoard,
long row, long col, Direction move);
// determines whether a given two-bridge is free
// PRECONDITIONS: (row, col) contains one of the pieces in
// in the two-bridge, move is the direction of the bridge,
// boardSize and theBoard define the board
// POSTCONDITIONS: returns true if the spaces in between
// are free; otherwise, returns false
Boolean PieceOnEdge(long row, long col, long boardSize,
Edge edge);
// determines whether a given piece is on a desired edge
// PRECONDITIONS: (row, col) indicate a piece, boardSize is
// the number of rows or columns on the board, edge is the
// desired edge
// POSTCONDITIONS: returns true if the piece is on the edge;
// otherwise returns false
void FreePath(Path *path);
// disposes the memory associated with a path
// PRECONDITIONS: path points to a path
// POSTCONDITIONS: the memory associated with the path is
// freed.
Boolean ValidMove(long boardSize, Chip *theBoard,
long row, long col);
// determines whether a desired move is legal
// PRECONDITIONS: boardSize contains the number of rows or
// columns on the board; theBoard defines the playing
// board; (row, col) is the location of the intended move
// POSTCONDITIONS: returns true if the piece is on the
// board and not already taken; otherwise false
Disruption MoveInPath(Path *path, long row, long col);
// determines whether a desired move is in a path
// PRECONDITIONS: path describes a path across the board;
// (row, col) defines the intended move
// POSTCONDITIONS: returns noDisruption if the move is
// not in the path, inTwoBridge if it threatens an
// established two-bridge, or inSpot if it occupies a
// location in the path (including a two-bridge whose
// end-points have not been secured)
Boolean TwoBridgeThreatened(long row, long col,
long threatRow, long threatCol, Direction move);
// determines whether a two-bridge is threatened by a given
// move
// PRECONDITIONS: (row, col) is the origin of a two-bridge;
// (threatRow, threatCol) is the new move; move is the
// direction of the two-bridge
// POSTCONDITIONS: returns true if the two-bridge is
// threatened by the move
void UpdatePath(Path *path, long row, long col);
// updates a path when a move is made
// PRECONDITIONS: path points to a path across the board;
// (row, col) is the location of the move
// POSTCONDITIONS: the location in the path is marked
// as being occupied; sometimes, as when a two-bridge
// is filled in (and destroyed), an extra node is added to
// the path list
Direction GetDirection(long row1, long col1, long row2,
long col2);
// determines the direction from one piece to another
// PRECONDITIONS: (row1, col1) and (row2, col2) define
// two pieces
// POSTCONDITIONS: the direction from (row1, col1) to
// (row2, col2) is returned
Path *BetterPath(Path *path1, Path *path2,
PathAction action);
// determines which of two paths is superior to the other
// PRECONDITIONS: path1 and path2 point to paths
// POSTCONDITIONS: the better of the two paths is returned;
// if action is forgetBad, then the inferior path is
// disposed
long PathRating(Path *path);
// rates a path
// PRECONDITIONS: path is a path
// POSTCONDITIONS: a rating for the path is returned
// (always positive, low numbers are better)
void FillThreatenedTwoBridge(Path *path, long threatRow,
long threatCol, long *row, long *col);
// determines where to move in order to secure a threatened
// two-bridge
// PRECONDITIONS: path points to a path;
// (threatRow, threatCol) is the move which threatened the
// two-bridge
// POSTCONDITIONS: (row, col) is the move needed to secure
// the free half of the two-bridge
Path *TakeDetour(long boardSize, Chip *theBoard, Path *path,
long row, long col, Chip color);
// finds a new path after it has been disrupted
// PRECONDITIONS: path points to a path; (row, col)
// indicates a move which disrupted the path
// POSTCONDITIONS: the path is corrected, if possible, so
// that it avoids the opponent's piece, and it is then
// returned; nil is returned if no new path can be found
void FindBestMove(Path *ourPath, Path *oppPath, long *row,
long *col);
// TRIES to determine the best move
// PRECONDITIONS: ourPath and oppPath are the expected
// paths of the player and the opponent, respectively
// POSTCONDITIONS: (*row, *col) indicate the chosen move,
// which should be decent; if the opponent's path is better,
// it should be a defensive move; if not, it should be
// an offensive move; whenever possible, offensive and
// defensive moves are made to coincide with one another
Boolean NextToEdge(long row, long col, long boardSize,
Edge edge);
// determines if a piece is next to a given edge
// PRECONDITIONS: (row, col) is a piece; boardSize is the
// size of the board, edge is the edge we want to be near
// POSTCONDITIONS: returns true if the piece if one hex
// from the edge
Boolean Hex(long boardSize, long oppRow, long oppCol,
long *moveRow, long *moveCol, void *privStorage,
Boolean newGame, Boolean playFirst);
Boolean Hex(long boardSize, long oppRow, long oppCol,
long *moveRow, long *moveCol, void *privStorage,
Boolean newGame, Boolean playFirst)
{
// board storage (preserved between turns)
static Chip *theBoard;
// expected paths (also preserved between turns)
static Path *ourPath, *oppPath;
// a temporary path used for comparisons
Path *newPath;
Disruption disruption; // holds path disruptions
if (newGame)
{
long i;
// initialize the private storage allocation system
InitializeHeap(privStorage, 0x100000); // 1 MB
// initialize storage space for the board
theBoard = AllocateBlock(boardSize * boardSize);
for (i = 0; i < boardSize * boardSize; i++)
theBoard[i] = empty;
// indicate that no paths have yet been determined
ourPath = oppPath = nil;
if (playFirst)
{
// go in the middle
*moveRow = (boardSize - 1) / 2;
*moveCol = boardSize / 2;
// mark the chip on the board
theBoard[*moveRow * boardSize + *moveCol] =
blue; // blue because we are moving first
// try to determine the shortest route across
// the board through the spot where we just
// moved
ourPath = BestPathAcrossBoard(boardSize,
theBoard, *moveRow, *moveCol, blue);
return true;
} // end if
} // end if
// check the opponent's move
if (!ValidMove(boardSize, theBoard, oppRow, oppCol))
// if it is illegal, abort here
return false;
// mark the opponent's move on the board
theBoard[oppRow * boardSize + oppCol] =
playFirst ? red : blue;
// if the opponent's move was in his path (offensive)
if (MoveInPath(oppPath, oppRow, oppCol))
// update his path
UpdatePath(oppPath, oppRow, oppCol);
else // opponent did not continue his expected path
{
// try to find a probable route for the
// opponent through the piece where he just
// moved
newPath = BestPathAcrossBoard(boardSize, theBoard,
oppRow, oppCol, playFirst ? red : blue);
// if his new route is better than his old one, use
// it instead
oppPath = BetterPath(oppPath, newPath, forgetBad);
} // end else
// determine whether his move blocked or
// otherwise disrupted our path
disruption = MoveInPath(ourPath, oppRow, oppCol);
if (disruption == inTwoBridge)
{
// move into the other half of the
// two-bridge automatically
FillThreatenedTwoBridge(ourPath, oppRow, oppCol,
moveRow, moveCol);
// mark the move on the board
theBoard[*moveRow * boardSize + *moveCol] =
playFirst ? blue : red;
// update the path
UpdatePath(ourPath, *moveRow, *moveCol);
} // end if
else // no automatic response
{
if (disruption == inSpot)
// try to find a new path from just
// before the disruption (the unaffected
// part of the path can remain)
ourPath = TakeDetour(boardSize, theBoard,
ourPath, oppRow, oppCol, playFirst ? blue :
red);
// try to determine the best move and then make it
FindBestMove(ourPath, oppPath, moveRow, moveCol);
// if the move was invalid (happens when neither
// player has a path), just try to find a
// valid move
if (!ValidMove(boardSize, theBoard, *moveRow,
*moveCol))
{
Boolean moveFound = false;
for (*moveRow = 0; !moveFound && *moveRow
< boardSize; (*moveRow)++)
{
for (*moveCol = 0; !moveFound && *moveCol
< boardSize; (*moveCol)++)
{
if (ValidMove(boardSize, theBoard,
*moveRow, *moveCol))
{
moveFound = true;
(*moveRow)--;
(*moveCol)--;
} // end if
} // end for
} // end for
} // end if
// mark the move on the board
theBoard[*moveRow * boardSize + *moveCol] =
playFirst ? blue : red;
// check to see if the move was in our path
if (MoveInPath(ourPath, *moveRow, *moveCol))
// if so, update it
UpdatePath(ourPath, *moveRow, *moveCol);
else
{
// otherwise, try to find a path through the
// new location
newPath = BestPathAcrossBoard(boardSize,
theBoard, *moveRow, *moveCol,
playFirst ? blue : red);
// if the new path is better than the
// old one, use it instead
ourPath = BetterPath(ourPath, newPath,
forgetBad);
} // end else
} // end if
// if our move blocked the opponent's path,
// try to find him a new path from just before
// the disruption
if (MoveInPath(oppPath, *moveRow, *moveCol))
oppPath = TakeDetour(boardSize, theBoard, oppPath,
*moveRow, *moveCol, playFirst ? red : blue);
return true;
} // end Hex
Path *BestPathAcrossBoard(long boardSize, Chip *theBoard,
long startRow, long startCol, Chip color)
{
// initial path is just the starting hex
Path *thePath = AllocateBlock(sizeof (Path));
thePath->row = startRow;
thePath->col = startCol;
thePath->occupied = // should be true always
theBoard[startRow * boardSize + startCol] == color;
// no connections yet
thePath->prev = thePath->next = nil;
thePath->prevDirection = thePath->nextDirection =
noDirection;
thePath->center = true;
// find the best path from (startRow, startCol) to the
// top (if blue) or left (if red) edge
if (!ExtendPathToEdge(boardSize, theBoard, thePath,
color == blue ? topEdge : leftEdge))
{
FreePath(thePath);
return nil;
} // end if
// find the best path from (startRow, startCol) to the
// other friendly edge
if (!ExtendPathToEdge(boardSize, theBoard, thePath,
color == blue ? bottomEdge : rightEdge))
{
FreePath(thePath);
return nil;
} // end if
// if we made it here, we succeeded
return thePath;
} // end BestPathAcrossBoard
Boolean ExtendPathToEdge(long boardSize, Chip *theBoard,
Path *path, Edge edge)
{
Direction moveList[12]; // stores the move priorities
// which color we are
Chip color = edge == leftEdge || edge == rightEdge ?
red : blue;
long moveNum; // an index for when we try to move
// which way the path is going
Boolean goingForward = edge == rightEdge ||
edge == bottomEdge;
Boolean result; // did we succeed yet
// prioritize the moves according to which edge we
// are seeking and the current location in the path
PrioritizeMoves(edge, moveList);
// stop if we are already at an edge
if (PieceOnEdge(path->row, path->col, boardSize, edge))
return true;
// see if we are next to the edge
if (NextToEdge(path->row, path->col, boardSize, edge))
{
Direction d;
long newRow, newCol;
// make the simplest move to reach the edge
for (d = right; d < noDirection; d++)
if (!IsTwoBridge(d))
{
FindNewLocation(path->row, path->col, d,
&newRow, &newCol);
if (PieceOnEdge(newRow, newCol, boardSize,
edge) && ValidMove(boardSize, theBoard,
newRow, newCol))
{
// allocate space for the new node
Path *newNode =
AllocateBlock(sizeof (Path));
newNode->row = newRow;
newNode->col = newCol;
// determine if it has been secured or
// not
newNode->occupied = theBoard[
newNode->row * boardSize +
newNode->col] == color;
// it is not the center (it is an
// extension)
newNode->center = false;
// link the new node to the old path
if (goingForward)
{
path->nextDirection = d;
path->next = newNode;
newNode->prevDirection =
OppositeDirection(d);
newNode->prev = path;
newNode->next = nil;
newNode->nextDirection =
noDirection;
} // end if
else
{
path->prevDirection = d;
path->prev = newNode;
newNode->nextDirection =
OppositeDirection(d);
newNode->next = path;
newNode->prev = nil;
newNode->prevDirection =
noDirection;
} // end else
return true;
} // end if
} // end for
} // end if
// first look to connect with a piece that is already
// on the board
for (result = false, moveNum = 0;
!result && moveNum < 9; moveNum++)
{
// once a single move works, try to extend from
// the new location to the same edge
if (PossibleMove(boardSize, theBoard, path->row,
path->col, path, moveList[moveNum], color))
{
// allocate space for the new node
Path *newNode = AllocateBlock(sizeof (Path));
// abort if there is not enough memory
if (!newNode)
return false;
// define its position
FindNewLocation(path->row, path->col,
moveList[moveNum], &newNode->row,
&newNode->col);
// determine if it has been secured or not
newNode->occupied = theBoard[newNode->row *
boardSize + newNode->col] == color;
// only make the move if there is already a
// connection
if (!newNode->occupied)
{
FreeBlock(newNode);
continue;
}
// it is not the center (it is an extension)
newNode->center = false;
// link the new node to the old path
if (goingForward)
{
path->nextDirection = moveList[moveNum];
path->next = newNode;
newNode->prevDirection =
OppositeDirection(moveList[moveNum]);
newNode->prev = path;
newNode->next = nil;
newNode->nextDirection = noDirection;
} // end if
else
{
path->prevDirection = moveList[moveNum];
path->prev = newNode;
newNode->nextDirection =
OppositeDirection(moveList[moveNum]);
newNode->next = path;
newNode->prev = nil;
newNode->prevDirection = noDirection;
} // end else
// see if we can get to an edge
if (ExtendPathToEdge(boardSize, theBoard,
newNode, edge))
{
result = true;
} // end if
else
{
// undo the added node
FreeBlock(newNode);
if (goingForward)
{
path->next = nil;
path->nextDirection = noDirection;
} // end if
else
{
path->prev = nil;
path->prevDirection = noDirection;
} // end else
} // end else
} // end if
} // end for
// try moves until we run out or one works
for (moveNum = 0; !result && moveNum < 7; moveNum++)
{
// once a single move works, try to extend from
// the new location to the same edge
if (PossibleMove(boardSize, theBoard, path->row,
path->col, path, moveList[moveNum], color))
{
// allocate space for the new node
Path *newNode = AllocateBlock(sizeof (Path));
// abort if there is not enough memory
if (!newNode)
return false;
// define its position
FindNewLocation(path->row, path->col,
moveList[moveNum], &newNode->row,
&newNode->col);
// determine if it has been secured or not
newNode->occupied = theBoard[newNode->row *
boardSize + newNode->col] == color;
// it is not the center (it is an extension)
newNode->center = false;
// link the new node to the old path
if (goingForward)
{
path->nextDirection = moveList[moveNum];
path->next = newNode;
newNode->prevDirection =
OppositeDirection(moveList[moveNum]);
newNode->prev = path;
newNode->next = nil;
newNode->nextDirection = noDirection;
} // end if
else
{
path->prevDirection = moveList[moveNum];
path->prev = newNode;
newNode->nextDirection =
OppositeDirection(moveList[moveNum]);
newNode->next = path;
newNode->prev = nil;
newNode->prevDirection = noDirection;
} // end else
// see if we are at the edge or can get to one
if (ExtendPathToEdge(boardSize, theBoard,
newNode, edge))
{
result = true;
} // end if
else
{
// undo the added node
FreeBlock(newNode);
if (goingForward)
{
path->next = nil;
path->nextDirection = noDirection;
} // end if
else
{
path->prev = nil;
path->prevDirection = noDirection;
} // end else
} // end else
} // end if
} // end for
// return true if we succeeded, false if not
return result;
} // end ExtendPathToEdge
void PrioritizeMoves(Edge edge, Direction move[12])
{
switch (edge)
{
case leftEdge:
// in order from most to least direct
move[0] = downLeftTwoBridge;
move[1] = upLeftTwoBridge;
move[2] = downTwoBridge;
move[3] = left;
move[4] = downLeft;
move[5] = upLeft;
move[6] = downRight;
move[7] = upRight;
move[8] = right;
move[9] = upTwoBridge;
move[10] = downRightTwoBridge;
move[11] = upRightTwoBridge;
break;
case rightEdge:
// in order from most to least direct
move[0] = upRightTwoBridge;
move[1] = downRightTwoBridge;
move[2] = upTwoBridge;
move[3] = right;
move[4] = upRight;
move[5] = downRight;
move[6] = upLeft;
move[7] = downLeft;
move[8] = left;
move[9] = downTwoBridge;
move[10] = upLeftTwoBridge;
move[11] = downLeftTwoBridge;
break;
case topEdge:
// in order from most to least direct
move[0] = upTwoBridge;
move[1] = upLeftTwoBridge;
move[2] = upRightTwoBridge;
move[3] = upLeft;
move[4] = upRight;
move[5] = left;
move[6] = right;
move[7] = downLeft;
move[8] = downRight;
move[9] = downLeftTwoBridge;
move[10] = downRightTwoBridge;
move[11] = downTwoBridge;
break;
case bottomEdge:
// in order from most to least direct
move[0] = downTwoBridge;
move[1] = downRightTwoBridge;
move[2] = downLeftTwoBridge;
move[3] = downRight;
move[4] = downLeft;
move[5] = right;
move[6] = left;
move[7] = upRight;
move[8] = upLeft;
move[9] = upRightTwoBridge;
move[10] = upLeftTwoBridge;
move[11] = upTwoBridge;
break;
default:
break; // should never arrive here
} // end switch
} // end PrioritizeMoves
Boolean PossibleMove(long boardSize, Chip *theBoard,
long row, long col, Path *path, Direction move,
Chip color)
{
long newRow, newCol; // where the move leads
// determine where a move in the new direction would
// lead
FindNewLocation(row, col, move, &newRow, &newCol);
// the new location must be on the board and either
// empty or occupied by a friendly piece; it must also
// not be in the path already
if (!OnBoard(boardSize, newRow, newCol)
|| (theBoard[newRow * boardSize + newCol] ==
(color == blue ? red : blue)) ||
MoveInPath(path, newRow, newCol))
return false;
// if the move forms a two-bridge, there must
// be no pieces in between the two
if (IsTwoBridge(move))
{
return TwoBridgeFree(boardSize, theBoard, row, col,
move);
} // end if
else
return true;
} // end PossibleMove
void FindNewLocation(long row, long col, Direction move,
long *newRow, long *newCol)
{
// handle the row first
switch (move)
{
case upTwoBridge:
*newRow = row - 2;
break;
case upRightTwoBridge:
case upRight:
case upLeft:
case upLeftTwoBridge:
*newRow = row - 1;
break;
case left:
case right:
*newRow = row;
break;
case downLeftTwoBridge:
case downLeft:
case downRight:
case downRightTwoBridge:
*newRow = row + 1;
break;
case downTwoBridge:
*newRow = row + 2;
break;
default: // should never get here
break;
} // end switch
// then handle the column
switch (move)
{
case downLeftTwoBridge:
*newCol = col - 2;
break;
case upLeftTwoBridge:
case left:
case downLeft:
case downTwoBridge:
*newCol = col - 1;
break;
case upLeft:
case downRight:
*newCol = col;
break;
case upTwoBridge:
case upRight:
case right:
case downRightTwoBridge:
*newCol = col + 1;
break;
case upRightTwoBridge:
*newCol = col + 2;
break;
default: // should never get here
break;
} // end switch
} // end FindNewLocation
Direction OppositeDirection(Direction move)
{
switch (move)
{
case upTwoBridge:
return downTwoBridge;
case upRightTwoBridge:
return downLeftTwoBridge;
case upRight:
return downLeft;
case upLeft:
return downRight;
case upLeftTwoBridge:
return downRightTwoBridge;
case left:
return right;
case right:
return left;
case downLeftTwoBridge:
return upRightTwoBridge;
case downLeft:
return upRight;
case downRight:
return upLeft;
case downRightTwoBridge:
return upLeftTwoBridge;
case downTwoBridge:
return upTwoBridge;
default: // should never get here
break;
} // end switch
} // end OppositeDirection
Boolean OnBoard(long boardSize, long row, long col)
{
return row >= 0 && row < boardSize && col >= 0 &&
col < boardSize;
} // end OnBoard
Boolean IsTwoBridge(Direction move)
{
switch (move)
{
case upTwoBridge:
case upRightTwoBridge:
case upLeftTwoBridge:
case downLeftTwoBridge:
case downRightTwoBridge:
case downTwoBridge:
return true;
default:
return false;
} // end switch
} // end IsTwoBridge
Boolean TwoBridgeFree(long boardSize, Chip *theBoard,
long row, long col, Direction move)
{
switch (move)
{
case upTwoBridge:
return theBoard[(row - 1) * boardSize + col] ==
empty && theBoard[(row - 1) * boardSize +
col + 1] == empty;
case upRightTwoBridge:
return theBoard[(row - 1) * boardSize +
col + 1] == empty && theBoard[row *
boardSize + col + 1] == empty;
case upLeftTwoBridge:
return theBoard[(row - 1) * boardSize +
col] == empty && theBoard[row *
boardSize + col - 1] == empty;
case downLeftTwoBridge:
return theBoard[(row + 1) * boardSize +
col - 1] == empty && theBoard[row *
boardSize + col - 1] == empty;
case downRightTwoBridge:
return theBoard[(row + 1) * boardSize +
col] == empty && theBoard[row *
boardSize + col + 1] == empty;
case downTwoBridge:
return theBoard[(row + 1) * boardSize +
col] == empty && theBoard[(row + 1) *
boardSize + col - 1] == empty;
default:
return false;
} // end switch
} // TwoBridgeFree
Boolean PieceOnEdge(long row, long col, long boardSize,
Edge edge)
{
switch (edge)
{
case leftEdge:
return col == 0;
case rightEdge:
return col == boardSize - 1;
case topEdge:
return row == 0;
case bottomEdge:
return row == boardSize - 1;
default: // should never get here
break;
} // end switch
} // end PieceOnEdge
void FreePath(Path *path)
{
if (!path)
return;
// go to the beginning of the path
for (; path->prev; path = path->prev);
// free each node until none are left
for (; path; path = path->next)
FreeBlock(path);
} // end
Boolean ValidMove(long boardSize, Chip *theBoard,
long row, long col)
{
return OnBoard(boardSize, row, col) &&
theBoard[row * boardSize + col] == empty; // free
} // end ValidMove
Disruption MoveInPath(Path *path, long row, long col)
{
if (!path)
return noDisruption;
// go to the beginning of the path
for (; path->prev; path = path->prev);
// search the path until the end is reached or a node
// is found matching the desired move
for (; path; path = path->next)
// check for a threatened two-bridge
if (IsTwoBridge(path->nextDirection) &&
TwoBridgeThreatened(path->row, path->col,
row, col, path->nextDirection))
{
if (path->occupied && path->next->occupied)
return inTwoBridge;
else
return inSpot;
} // end if
else if (row == path->row && col == path->col)
return inSpot;
// if we get here, there are no disruptions
return noDisruption;
} // end MoveInPath
Boolean TwoBridgeThreatened(long row, long col,
long threatRow, long threatCol, Direction move)
{
switch (move)
{
case upTwoBridge:
return (threatRow == row - 1) &&
(threatCol == col || threatCol == col + 1);
case upRightTwoBridge:
return (threatCol == col + 1) &&
(threatRow == row - 1 || threatRow == row);
case upLeftTwoBridge:
return (threatRow + threatCol == row + col - 1)
&& (threatRow == row || threatCol == col);
case downLeftTwoBridge:
return (threatCol == col - 1) &&
(threatRow == row || threatRow == row + 1);
case downRightTwoBridge:
return (threatRow + threatCol == row + col + 1)
&& (threatRow == row || threatCol == col);
case downTwoBridge:
return (threatRow == row + 1) &&
(threatCol == col || threatCol == col - 1);
default: // should not get here
return false;
} // end switch
} // end TwoBridgeThreatened
void UpdatePath(Path *path, long row, long col)
{
// go to the beginning of the path
for (; path->prev; path = path->prev);
// search the path until the end is reached or a node
// is found matching the desired move
for (; path; path = path->next)
// check for completion of a two-bridge
if (IsTwoBridge(path->nextDirection) &&
TwoBridgeThreatened(path->row, path->col,
row, col, path->nextDirection))
{
// destroy the two-bridge and create two new
// connections
Path *newNode = AllocateBlock(sizeof (Path));
newNode->row = row;
newNode->col = col;
newNode->occupied = true;
newNode->center = false;
newNode->prevDirection = GetDirection(
row, col, path->row, path->col);
newNode->nextDirection = GetDirection(
row, col, path->next->row, path->next->col);
newNode->prev = path;
newNode->next = path->next;
path->nextDirection = OppositeDirection(
newNode->prevDirection);
path->next = newNode;
newNode->next->prevDirection =
OppositeDirection(newNode->nextDirection);
newNode->next->prev = newNode;
} // end if
else if (row == path->row && col == path->col)
path->occupied = true;
} // end UpdatePath
Direction GetDirection(long row1, long col1, long row2,
long col2)
{
// check for unique cases first
if (row2 == row1 + 2)
return downTwoBridge;
else if (row2 == row1 - 2)
return upTwoBridge;
else if (col2 == col1 + 2)
return upRightTwoBridge;
else if (col2 == col1 - 2)
return downLeftTwoBridge;
// then try the more common ones
else if (row2 == row1 - 1)
if (col2 == col1 - 1)
return upLeftTwoBridge;
else if (col2 == col1)
return upLeft;
else // col2 == col1
return upRight;
else if (row2 == row1 + 1)
if (col2 == col1 - 1)
return downLeft;
else if (col2 == col1 + 1)
return downRightTwoBridge;
else // col2 == col1
return downRight;
else // row2 == row1
if (col2 == col1 - 1)
return left;
else // col2 == col1 + 1
return right;
} // end GetDirection
Path *BetterPath(Path *path1, Path *path2,
PathAction action)
{
long rating1, rating2;
Path *betterPath, *worsePath;
// rate both paths
rating1 = PathRating(path1);
rating2 = PathRating(path2);
// compare the ratings (low is better)
if (rating1 < rating2)
{
betterPath = path1;
worsePath = path2;
} // end if
else
{
betterPath = path2;
worsePath = path1;
} // end else
// dispose of the bad path, if directed to do so
if (action == forgetBad)
FreePath(worsePath);
return betterPath;
} // end BetterPath
long PathRating(Path *path)
{
long rating;
if (!path)
return 4096;
// go to the beginning of the path
for (; path->prev; path = path->prev);
// count the number of unoccupied locations
for (rating = 0; path; path = path->next)
if (path->occupied == false)
rating++;
return rating;
} // end PathRating
void FillThreatenedTwoBridge(Path *path, long threatRow,
long threatCol, long *row, long *col)
{
// go to the beginning of the path
for (; path->prev; path = path->prev);
// scan through the path until the threat is found
for (; path; path = path->next)
if (IsTwoBridge(path->nextDirection) &&
TwoBridgeThreatened(path->row, path->col,
threatRow, threatCol, path->nextDirection))
{
// try all moves until we find one that fills
// the two-bridge (sorry, it's the easiest way
// way to do it)
Direction d;
Boolean done;
for (done = false, d = 0; !done &&
d < noDirection; d++)
{
FindNewLocation(path->row, path->col,
d, row, col);
// make sure we're not making the same move
// as the opponent
if (TwoBridgeThreatened(path->row,
path->col, *row, *col,
path->nextDirection) && (*row !=
threatRow || *col != threatCol))
{
done = true;
} // end if
} // end for
} // end if
} // end FillThreatenedTwoBridge
Path *TakeDetour(long boardSize, Chip *theBoard, Path *path,
long row, long col, Chip color)
{
Boolean centerPassed; // have we passed the center?
Boolean blockFound; // have we located the disruption?
Path *corruptPath; // the part that was blocked
Edge edge;
// go to the beginning of the path
for (; path->prev; path = path->prev);
// find the location of the disruption
for (centerPassed = blockFound = false; path &&
!blockFound;)
{
if (path->center)
centerPassed = true;
if (IsTwoBridge(path->nextDirection) &&
TwoBridgeThreatened(path->row, path->col,
row, col, path->nextDirection))
{
if (centerPassed)
path = path->next;
blockFound = true;
} // end if
else if (row == path->row && col == path->col)
blockFound = true;
else
path = path->next;
} // end for
// free from there to the end
if (centerPassed)
{
corruptPath = path;
path = path->prev;
path->next = corruptPath->prev = nil;
FreePath(corruptPath);
} // end if
else
{
corruptPath = path;
path = path->next;
corruptPath->next = path->prev = nil;
FreePath(corruptPath);
} // end else
if (color == blue)
if (centerPassed)
edge = bottomEdge;
else
edge = topEdge;
else // color is red
if (centerPassed)
edge = rightEdge;
else
edge = leftEdge;
// extend the path from there to the edge
if (!ExtendPathToEdge(boardSize, theBoard, path, edge))
{
// if not possible, destroy the path
FreePath(path);
path = nil;
} // end if
return path;
} // end TakeDetour
void FindBestMove(Path *ourPath, Path *oppPath, long *row,
long *col)
{
// ratings for our path, the opponent's path, and the
// two halves of the better (used) path
long ourRating, oppRating, prevRating = 0,
nextRating = 0;
Path *usedPath, *tempPath, *unusedPath;
// don't even try to continue if there are no paths
if (!oppPath && !ourPath)
return;
// see who has the better path
ourRating = PathRating(ourPath);
oppRating = PathRating(oppPath);
if (ourRating < oppRating) // ours is better
{
usedPath = ourPath;
unusedPath = oppPath;
}
else
{
usedPath = oppPath;
unusedPath = ourPath;
}
// first try to make a move which is both offensive
// and defensive
tempPath = usedPath;
// go to the beginning
for (; tempPath->prev; tempPath = tempPath->prev);
// find the first unoccupied piece
for (; tempPath && tempPath->occupied;
tempPath = tempPath->prev)
{
// see if it is in the other path, also
if (MoveInPath(unusedPath, tempPath->row,
tempPath->col))
{
*row = tempPath->row;
*col = tempPath->col;
return;
}
}
// look for unoccupied pieces
tempPath = usedPath;
// go to the beginning
for (; tempPath->prev; tempPath = tempPath->prev);
// go to the center
for (; !tempPath->center; tempPath = tempPath->next);
// rate the first half
for (; tempPath; tempPath = tempPath->prev)
prevRating += !tempPath->occupied;
tempPath = usedPath;
// go to the beginning
for (; tempPath->prev; tempPath = tempPath->prev);
// go back to the center
for (; !tempPath->center; tempPath = tempPath->next);
// rate the second half
for (; tempPath; tempPath = tempPath->next)
nextRating += !tempPath->occupied;
tempPath = usedPath;
// go to the beginning
for (; tempPath->prev; tempPath = tempPath->prev);
// go to the center
for (; !tempPath->center; tempPath = tempPath->next);
// make a move on the side with the worse (high) rating
if (prevRating > nextRating)
// find the first unoccupied piece
for (; tempPath && tempPath->occupied;
tempPath = tempPath->prev);
else
// find the first unoccupied piece
for (; tempPath && tempPath->occupied;
tempPath = tempPath->next);
if (tempPath)
{
*row = tempPath->row;
*col = tempPath->col;
} // end if
else // no unoccupied pieces anywhere
{
// if there are none, fill in any unconnected
// two-bridges
for (; usedPath->prev; usedPath =
usedPath->prev);
for (; usedPath && !IsTwoBridge(
usedPath->nextDirection);
usedPath = usedPath->next);
if (usedPath) // should always be true
{
// try all moves until we find one that
// fills the two-bridge (sorry, it's the
// easiest way way to do it)
Direction d;
Boolean done;
for (done = false, d = 0; !done &&
d < noDirection; d++)
{
FindNewLocation(usedPath->row,
usedPath->col, d, row, col);
if (TwoBridgeThreatened(usedPath->row,
usedPath->col, *row, *col,
usedPath->nextDirection))
{
done = true;
} // end if
} // end for
} // end if
} // end else
} // end FindBestMove
Boolean NextToEdge(long row, long col, long boardSize,
Edge edge)
{
switch (edge)
{
case leftEdge:
return col == 1;
case rightEdge:
return col == boardSize - 2;
case topEdge:
return row == 1;
case bottomEdge:
return row == boardSize - 2;
default: // should never get here
break;
} // end switch
} // end NextToEdge